\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}
\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{216}
Investigating the primality of numbers of the form $2 n^2-1$.

Consider numbers $t(n)$ of the form $t(n) = 2n^2-1$ with $n > 1$.
The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161.
It turns out that only $49 = 7 \times 7$ and $161 = 7 \times 23$ are not prime.

For $n \le 10000$ there are 2202 numbers $t(n)$ that are prime.

How many numbers $t(n)$ are prime for $n \le 50,000,000$?

\solution

We use a Sieve method to solve the problem. The core idea of sieving is that for each prime number $p$, we eliminate $p$ from all terms in the sequence. The requirement is that we have a fast way to determine which terms contain the factor $p$. In this way the time complexity of the solution will be equal to the total number of prime factors in the sequence, which is manageable.

Suppose prime $p$ divides $t(m)$ and $t(n)$ where $m<n$. Then we have
\[
2 m^2-1 \equiv 2 n^2-1 \text{ (mod $p$)} .
\]
Rearranging terms, we get
\[
2(n-m)(n+m) \equiv 0  \text{ (mod $p$)} .
\]
Since all $t(n)$ are odd, $p \ne 2$. Therefore the above equation leads to
\[
n \equiv m \text{ or } n \equiv p-m \text{ (mod $p$)} .
\]
It can be shown that these two classes do not overlap, because otherwise we would have $m \equiv p-m$, hence $m \equiv 0$ (mod $p$), which is contradictory.

The sieving process is as follows. First, initialize an array $t_n=2 n^2-1$ for $2 \le n \le N$. Then, for each $n$ starting from 2 through $N$: if $t_n>1$, then we eliminate $p=t_n$ from every $t_{n+lp}$ for $1 \le l \le \lfloor (N-n)/p \rfloor $ and from $t_{lp-n}$ for $1 \le l \le \lfloor (N+n)/p \rfloor$. At the same time, if $t_n = 2n^2-1$ (i.e. the term has never been reduced), then it is a prime and we increase the counter. Continue until $n = N$.

The correctness of the algorithm is shown below. When we come to $t_n$, we claim that all primes $p<2n$ are already eliminated. This is because

1) If $p<n$ divides $t_n$, then $p$ also divides $t_{n-p}$ and thus would have been eliminated;

2) Obviously $p=n$ does not divide $t_n=2 n^2-1$;

3) If $n<p<2n$ divides $t_n$, then $p$ also divides $t_{p-n}$ and thus would have been eliminated.

This leaves us with $p \ge 2n$ as possible factors of $t(n)$. However, in this case $p^2 \ge 4n^2 > t(n)$, so $t(n)$ must be a prime itself.

\answer
5437849

\complexity

Time complexity: $\mathcal{O}(n \ln \ln n)$. This upper bound is found as follows. We use $n$ iterations to initialize $\{t_n\}$. Then we run a loop to eliminate all the prime factors of all terms in $\{t_n\}$. The total number of eliminations to perform is equal to the total number of prime factors of all the terms. Since the number of prime factors of $n$, $\Omega(n) \sim \ln \ln n$, we have $\Omega(2 n^2-1) \sim \ln \ln n$. Since there are $n$ terms, the upper bound is $n \ln \ln n$.

Space complexity: $\mathcal{O}(n)$

\noindent{\sc Notes.}

Due to the particular form of $t(n)$, it has been shown that we can find the terms that contain a given prime factor $p$ quickly. Details can be found on Project Euler's website. The improved algorithm can reduce space complexity to $1/64$ of that of the above algorithm.

\end{document}
